// https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/

class Solution
{
public:
  // 最终数组的大顶堆，从左往右，a[0] 就是堆中最大的元素
  void maxHeapify(vector<int> &a, int i, int heapSize)
  {
    /**
     *     largest = i
     *      /   \
     *  1*2+1   i*2+2
     */
    int l = i * 2 + 1; // i 左孩子
    int r = i * 2 + 2; // i 右孩子
    int largest = i; // 默认把传入的 i 当做当前堆的 root 节点

    // 最大 left 孩子
    if (l < heapSize && a[l] > a[largest])
    {
      largest = l;
    }

    // 最大 right 孩子
    if (r < heapSize && a[r] > a[largest])
    {
      largest = r;
    }

    // 如果【最大】并不是 i（root 节点），那么【调整】堆
    if (largest != i)
    {
      // 先交换元素
      swap(a[i], a[largest]);

      // 再调整堆
      maxHeapify(a, largest, heapSize);
    }
  }

  // 就是将一个数组，构造成一个堆
  void buildMaxHeap(vector<int> &a, int heapSize)
  {
    // 循环按照 heapSize/2 构造 大顶堆
    for (int i = heapSize / 2; i >= 0; --i)
    {
      maxHeapify(
        a, // 要构造堆的数组
        i,
        heapSize // 堆的总元素个数
      );
    }
  }

  int findKthLargest(vector<int> &nums, int k)
  {
    int heapSize = nums.size();

    // 构建一个大跟堆
    buildMaxHeap(nums, heapSize);

    /**
     * 输入: [3,2,1,5,6,4] 和 k = 2
     * 输出: 5
     *
     * 第 K 大元素，实际上是【总节点数为 K】的大顶堆数组 arr[0] 元素值，
     * 所以从【后】往【前】删除、调整 大顶堆，
     * 最终 arr[0] 就是【第 K 大】元素
     */
    int i = nums.size() - 1
    for (; i >= (nums.size() - k + 1); --i)
    {
      // 将当前【被删除】节点值，写入到 arr[0] 大顶堆 root 节点
      swap(nums[0], nums[i]);

      // 减少 大顶堆 长度
      --heapSize;

      // 调整 大顶堆
      maxHeapify(
        nums,
        0, // i=0 大顶堆 root 节点
        heapSize
      );
    }

    return nums[0];
  }
};